In relational database systems, it is important to create indexes on columns of the tables in the database. It is well-known that the efficiency of relational operations such as the JOIN operation or the evaluation of query constraints (SELECTION) is improved if the relevant columns of the table across which the operation take place are indexed. From the point of view of speeding query processing, it is desirable to have available indexes for all columns (and combinations) of all tables in a relational database.
In relational database systems, it is important to be able to efficiently add new data to an existing database. The addition of data to the table space may involve not only the addition of data, but the maintenance of indexes. The indexes for the existing data will be merged with the indexes for the data to be added.
For very small collections of data a merger of relational data tables and indexes may not pose a significant problem. For large data sets, however, the merging of the new data with the existing data, and the merging of associated indexes into the resultant table may be constrained by system limitations. The internal machine memory may be too small to accommodate the data structures that are being merged, resulting in time-expensive swapping of data from larger but slower data storage devices (typically magnetic disks).
Relational database indexing schemes are developed to permit the rapid execution of relational operations on the relational data. The techniques for maintaining relational database indexes will depend on the structure of the indexes to be merged.
One type of data structure which is of use in indexing relational data is the sort vector data structure. In the co-pending application entitled "Indexing Databases For Efficient Relational Querying", naming Mariano Consens as inventor, and Joint Technology Corpomdon as assignee, a collection of data structures is described that indexes all the columns on all the tables of a database in a space and time efficient manner. The co-pending application describes the use of sort vector files, and associated join bit files in art index structure for relational databases. The use of sort vectors is not restricted to such applications, however, and issues relating to the merger of sort vector indexes have a wider application.
Because sort vectors are by definition self-referential, the merging of such data structures presents efficiency issues. To follow the self-referential pointers in large sort vector data structures may result in slow performance for database systems which rely on sort vector structures in the indexes. This is particularly true for large indexes.
It is therefore desirable to have a computer system which permits sort vector data structures to be merged efficiently. In particular, a method which avoids the need to follow the self-referential pointers in both the sort vectors to be is merged is desirable.